package 题目集.线段树or树状数组.线段树;

import java.util.Arrays;
import java.util.Scanner;

//https://www.acwing.com/problem/content/description/1217/
//获取前方比自己大的人数，后方比自己小的人数，即是自己交换的次数
//由题知：所有人的高度<=1000000，所以我们可以构建一个身高频率表，当求第i个小朋友前面比自己高的人，其实就是获取 0~h[i]之间的所有身高的和
public class 小朋友排队_线段树 {

    static int[] tree;
    static int[] task;
    static final int N = 1000002;

    public static void initTree() {
        int len = (int) (Math.ceil(Math.log(N) / Math.log(2)) + 1);
        len = (int) Math.pow(2, len);
        tree = new int[len];
        task = new int[len];
    }

//    public static void build(int s, int l, int r) {
//        if (l == r) {
//            tree[s]=原始数组[s]
//            return;
//        }
//        int m = l + r >> 1;
//        build(s << 1, l, m);
//        build(s << 1 | 1, m + 1, r);
//        fromDown(s);
//    }

    public static void add(int s, int l, int r, int L, int R, int v) {
        if (L <= l && R >= r) {
            task[s] += v;
            tree[s] += v * (r - l + 1);
            return;
        }
        int m = l + r >> 1;
        pushDown(s, m - l + 1, r - m);  //因为是左闭右闭，所以左侧应该包含m，而右侧不包含
        if (L <= m) {   //因为左孩子包含了m
            add(s << 1, l, m, L, R, v); //左闭右闭，所以左区间是l,m
        }
        if (R > m) {
            add(s << 1 | 1, m + 1, r, L, R, v); //左闭右闭，右区间m+1,r
        }
        fromDown(s);
    }

    public static int query(int s, int l, int r, int L, int R) {
        if (L <= l && R >= r) {
            return tree[s];
        }
        int res = 0;
        int m = l + r >> 1;
        pushDown(s, m - l + 1, r - m);
        if (L <= m) {
            res += query(s << 1, l, m, L, R);
        }
        if (R > m) {
            res += query(s << 1 | 1, m + 1, r, L, R);
        }
        return res;
    }

    /**
     * 对s节点进行向下更新
     * @param ln：s节点左孩子有多少个数
     * @param rn：s节点右孩子有多少个数
     */
    public static void pushDown(int s, int ln, int rn) {
        if (task[s] == 0) return;
        int l = s << 1;
        if (l < tree.length) {
            task[l] += task[s];
            tree[l] += task[l] * ln;
        }
        if ((l | 1) < tree.length) {
            task[l | 1] += task[s];
            task[l | 1] += task[l | 1] * rn;
        }
        task[s] = 0;
    }

    //收割子节点
    public static void fromDown(int s) {
        tree[s]=0;
        int mi = s << 1;
        if (mi < tree.length) {
            tree[s] += tree[mi];
        }
        if ((mi | 1) < tree.length) {
            tree[s] += tree[mi | 1];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];  //0位置记录身高，1位置记录次数
        initTree();
        for (int i = 0; i < n; i++) {   //统计前面比他高的有多少个
            int v = sc.nextInt();
            arr[i][0] = v;
            add(1, 0, N, v, v, 1);  //在v-v区间++
            if (v + 1 > N - 2) continue;
            arr[i][1] += query(1, 0, N, v + 1, N - 1);  //查找比他它高的人
        }
        initTree();
        for (int i = n - 1; i >= 0; i--) {  //统计后面比他矮的有多少个
            int v = arr[i][0];
            add(1, 0, N, v, v, 1);
            if (v - 1 < 0) continue;
            arr[i][1] += query(1, 0, N, 0, v - 1);  //查找比他它矮的人
        }
        long res = 0;
        for (int[] num : arr) {
            res += (1L + num[1]) * num[1] / 2;
        }
        System.out.println(res);
    }
}
